A significant number of cloud applications are network intensive, thus requiring the transmission of large amounts of data between the machines on which they are hosted. Examples of such cloud applications include data parallel applications such as MapReduce jobs, multi-tier web applications, analytic database workloads, storage/backup services, and scientific applications. These applications usually include several inter-related components and operate across dozens of machines. Without a network-aware system for placing workload, the cloud network resources can become a bottleneck for such network-intensive applications—even in well-provisioned clouds. Therefore, to make maximum use of cloud resources, it is of utmost importance not only to efficiently schedule cloud computation resources (e.g., processing, memory, storage, etc.), but also to make efficient use of the networking resources.
However, performing network-aware service placement is not a simple task, and is especially difficult for large-scale cloud infrastructures. A large-scale cloud infrastructure, typically distributed across the world, can include hundreds of thousands of servers and have complex hierarchical network infrastructures to accommodate the workload of cloud applications. Theoretically, such a large-scale cloud could be modeled as a large and complex multi-graph, where the computational resources represent vertices, the available resources on each server are the label of the vertices, and the network across different servers is represented as edges of the graph. Similarly, a service request with multiple tasks, and a network across tasks can be modeled as a graph. Then, the service placement in the cloud can be naturally modeled as a subgraph matching problem, where the goal is to return a network-efficient subgraph of the cloud graph, which is structurally and semantically isomorphic to the service (application) graph. Unfortunately, subgraph matching problem is NP-hard, and current attempts proceeding in this direction do not scale up to contemporary, cloud-size graphs. Further, as a cloud's available resources and the network links can vary over time, the problem of service placement is complicated further. In particular, it is difficult to directly adapt graph theory solutions to accommodate changing conditions because it is hard to collect frequently-changing network available information.
Some existing techniques adapt graph algorithms such as subgraph matching, shortest path and multi-commodity flow problems, etc., to design network-aware cloud service placement. However, these solutions do not scale up to cloud-size graphs and further require accurate network topology and network resource information, which is not always practical in clouds given the time-varying nature of a cloud's available resources.
As one example a technique proposed by Zong et al. (see Bo Zong, Ramya Raghavendra, Mudhakar Srivatsa, Xifeng Yan, Ambuj K. Singh, Kang-Won Lee, “Cloud service placement via subgraph matching”, 2014 IEEE 30th International Conference on Data Engineering (ICDE), pp. 832-843) adapts index-based subgraph matching solutions to perform cloud resource placement. This technique models the cloud as a graph and preforms offline graph indexing in order to explore frequent fragments of the cloud graph. It also maintains and updates the cloud available information in a grid structure. Upon receiving a service request, it explores the existing fragments and searches the grid in order to find a subgraph that is isomorphic to the service request. Graph-index based solutions, however, do not scale for cloud-scale graphs because: (i) indexing the graphs to find the frequent fragments is a costly operation, (ii) a large number of fragments leads to a large index size, and (iii) queries that do not contain frequent fragments are not well-supported. Further, this proposal assumes that the cloud network and resource information can be frequently updated using some sort of centralized monitoring tool. However, such a monitoring tool inflicts large network and memory overhead to the system, and thus is not practical.
Another example proposed by Xin et al. (see Y. Xin, I. Baldine, A. Mandal, C. Heermann, J. Chase, and A. Yumerefendi, “Embedding virtual topologies in networked clouds”, ACM, 2011, 6th International Conference on Future Internet Technologies, pp. 26-29) includes adapting existing subgraph matching solutions to solve cloud virtual network embedding. In particular, this proposed system focuses upon how to distribute the virtual network across multiple distributed clouds, where every cloud is assumed to be one node of the graph. However, this solution suffers from the scalability problems that exist for the existing subgraph matching solutions it adapts when solving for a large-scale distributed cloud.
Further, another example proposed by Yu et al. (see M. Yu, Yi, Y., Rexford, J., & Chiang, M., “Rethinking virtual network embedding: substrate support for path splitting and migration.” ACM SIGCOMM Computer Communication Review, 38(2), 17-29.) adapts multi-commodity flow problem and shortest path in order to find exact network paths for placing a service in a cloud. In this work, the assumption is that the location of the tasks is already set; the solution then takes into account the exact network topology and utilizes either shortest path or multi-commodity flow problem to find the exact paths. However, the cloud network topology is very complex and it is not always practical to make a network path reservation for a service.
Additionally, although there are a wide range of cloud platforms in active use, these solutions either separately solve for network and computation resources, or fundamentally rely upon overprovisioning of the network resources.
Accordingly, techniques are desired for performing network-aware service placement to efficiently utilize the cloud network resources without requiring the exact cloud network topology or a graph representing it. Also, such techniques are desired that do not dictate any network reservation, which is not always an option for data centers. Further, techniques are desired that do not rely upon having, at a central location, access to real-time network information.